Relationship between Generalized Origin Destination and Flow Matrix – A Tutorial
Kardi Teknomo
http://people.revoledu.com/kardi/
What is lacking from graph theory in general is the existence of moving agents. Moving agents create trajectories. Based on the ordinal graph trajectories that utilize the network, I have related the structure of a graph (e.g. adjacency matrix or path distance matrix) with the utilization of the graph (e.g. flow matrix or origin-destination matrix) by the agents. In summary, the relationship between network structure and network utilization can be simplified into simple algebraic equation of element wise product of the matrices and matrix addition:
Where the utilization matrices are
= generalized origin-destination matrix
= flow matrix
= alternative route matrix
and the network structure is represented by
= adjacency matrix.
When there is no alternative route, the formula is even shorter
.
I have related the structure of a graph (e.g. adjacency matrix or path distance matrix) with the utilization of the graph (e.g. flow matrix or origin-destination matrix) by the agents. In this tutorial, I give 2 numerical examples of the key concepts presented in our paper.
This tutorial is a companion of our paper in ATR (Teknomo, K. and Fernandez, P., A theoretical foundation for the relationship between generalized origin–destination matrix and flow matrix based on ordinal graph trajectories, Journal of Advance Transportation Research DOI: 10.1002/atr.1214). It is recommended to read the full paper from Wiley. Personal copy of the published paper is available upon request.
The topic of this tutorial is as follow:
Relationship between Network Structure and Network Utilization
Relationship between Network Structure and Network Utilization
Several interesting concepts we presented in our paper are as follow:
· Generalized Origin-Destination (OD) matrix is the superset of traditional Origin-Destination matrix in which every node in the network is considered as either source or sink. Generalized OD can be obtained and updated from tracking devices installed in probe vehicles such as public utilities vehicles, taxis and commercial vehicles as well as private cars.
· Given trajectories on the physical network from any tracking devices such as GPS, mobile phone, RFID, blue tooth, video camera and soon, it is possible to obtain the flow matrix and generalized origin destination matrix directly from these trajectories. We presented two algorithms to obtain the flow matrix and generalized origin destination matrix from trajectories.
· Transportation network can be categorized into two parts: the network structure (such as physical road network or pedestrian network) and the network utilization (how the network is utilized by agents such as cars or pedestrians).
· The network structure is represented by adjacency matrix, path
matrix
, external matrix
· The network utilization is represented by generalized origin-destination
matrix, flow matrix, alternative route matrix and substitute
route flow matrix 
and desire lines or indirect flow matrix
.
· Adjacency matrix is a subset of path matrix and therefore
adjacency matrix is always less than or equal to path matrix
.
· Therefore, we can get the difference between adjacency matrix and
path matrix, to what I called as External Matrix
.
· Flow-set matrix is a subset of the corresponding
Generalized Origin-Destination-set matrix and therefore Flow matrix is
less than or equal to generalized origin destination matrix
.
· Desire line in transportation network can be drawn based on indirect flow matrix
.
· When there is no alternative route flow, we can find the
relationship between network structure and network utilization as simple as
element wise product of the matrices
.
· When there is alternative route flow, we can find the
relationship between network structure and network utilization as simple as
.
· Alternative route flow matrix 
counts the number of
agents that pass through other routes other than the corresponding direct link.
· More comprehensive relationship between network structure and network utilization are given by the following formulas which proofs can be found in the paper.
|
|
|
|
Numerical Examples
The first example is a simple weaving section where the network is acyclic and there is only one direction. The trajectories are set so that the lengths of trajectories length are equal and there is no alternative route flow. The second example is a general network graph with trajectories of unequal length.
1. Weaving section
Suppose we have a simple weaving section consisting of 8 nodes and 8 links. For simplicity, without losing generality, we consider only 9 agents and generate 9 ordinal trajectories to be put into the network. The trajectories consist of 4 types in this simple network, but we repeat some of the trajectories. The adjacency matrix, the network and trajectories are given in the following figure. Zeroes in the matrix are deleted to enhance the pattern of non-zero entries. The non-zero entries are located on the upper diagonal to indicate that it is acyclic directed graph. The upper triangular property, however, is very much dependent on the labeling of the nodes. For example, if we swapped the labeling of the nodes ‘a’ and ‘h’, then the non-zero entries will not be restricted to the upper triangular, even though the graph is still a directed acyclic graph. See Buckley &Harary (1990) for proof that acyclic directed graph can be labeled as upper triangular of the adjacency matrix.
From the network structure, the path matrix isgiven below as computed using a simple breadth-first search approach using the adjacency matrix as input. Again, the zeroes are deleted from the matrices to enhance the view. Infinite elements indicate there exists no path between the two nodes. The maximum non-infinity entries represent the diameter of the network (which is 3 in this case). Binarized path matrix is the matrix that results from transforming all non-zero and non-infinity elements into one.
On the network structure, we can also define external matrix as the difference between path matrix and adjacency matrix. In the binarized external matrix, all non-zero and non-infinity elements of external matrix are also transformed to one
Now we discuss how the network is
utilized by putting ordinal graph trajectories into the network. Matrix-set
(with tilde) is a matrix in which entries are sets of trajectories. The matrix 
represents the set
of trajectories passing through a given direct link. The matrix and its
associated figure are shown below where the set of trajectory ids are placed on
each link. For instance, link ac is used by trajectories id {1, 3, 5, 7,
9}.
When we count the number of elements of sets of trajectory ids on each link, we get the flow matrix. Associated with the flow matrix is the flow pattern on each link as shown in the figure below. The number on each link is the explicit number of trajectories passing through that particular link. We also put the number visually as the weight of the arrow as flow pattern.
A trajectory passes through a
sequence of nodes from a source to a sink. Any ordered two nodes of the node
sequence of a trajectory can be seen as origin and destination nodes. For
instance, trajectory #1 of a->c->e->g will produce origin destination
pair nodes of {a->c, a->e, a->g, c->e, c->g, e->g}. Putting
these OD pair nodes into matrix produces origin-destination-set matrix 
. The entries of
this matrix are set of trajectory ID numbers of the OD pair nodes. Equation (14) formalizes the formulas
to obtain the origin-destination-set matrix through the intersection between
two sets of trajectories: a trajectories that goes out of a node origin and a
set of trajectories that goes in to a node destination.
The tilde notation represents a matrix whose elements are sets instead of scalar values. If we count the number of elements in each set in the matrix, we get the OD matrix
Since
, then we have. Clearly, we can
see that 
.
Considering only sources and sinks as in traditional OD matrix, we take partial
element of the matrix 
and
the associated OD produces graphs as shown below.
Now we exclude matrix set
Then we get the count of the elements in each set in the matrix to obtain
The Hadamard product of the binarized eternal matrix with the OD matrix will also produce the desire line matrix because there is no alternative route flow. The desire line pattern visualization is also shown below.
2. General Network Graph
The second numerical illustration involves a simple but general network with 7 nodes and 16 directed links. We also generate 9 arbitrary ordinal graph simple trajectories (without loop) to be placed in the network. Every link on the network is passed by at least one trajectory.
The network structure can be represented by 3 types of matrices: adjacency matrix, path matrix and external matrix. The adjacency matrix of the network is shown below together with its path matrix. Zeros in the matrices are deleted so that the reader can see the pattern of the matrix structure better. Notice that the non-zero and non-infinity entries are located on non-diagonal positions of the path matrix to indicate that there is path from any node to any other nodes in the network. The diagonals are zero because we do not have internal self-loop structure.
The external matrix is obtained from the path matrix by removing the direct links structure (i.e. adjacency matrix). In this case, we eliminate all one entries from the path matrix. The matrix-structure can be enhanced by binarizing the matrix.
In utilizing the network, we now put the nine trajectories of our example into the network.Note that the 3 loops in trajectory #6. In the sketch the trajectory number is drawn as an exponent to show the number of loops to the readers. In the matrix set of trajectories and the computation, however, the loop on trajectory is simply represented as single loop in the set because members of a set are unique. This representation makes sense because our ordinal graph trajectory actually comes from dynamic trajectory. The agent will not be present more than once in a given link at a given time. Therefore, a unique representation of each trajectory is necessary.
Flow set matrix indicates the trajectory ids that pass through direct links in the network. Empty set elements occur when there is no direct link.
Counting the number of elements in each set of the flow set matrix produces flow matrix that can be visualized using a flow pattern.
Intersecting the trajectory sets that go out of a node and trajectories that go in to a node produces OD- set matrix. For instance, trajectory #1 of a->b->c->e->g->f will produce origin destination pair nodes of {a->b, a->c, a->e, a->g, a->f, b->c,b->e, b->g,b->f, c->e, c->g, c->f, e->g, e->f, g-f}. Putting the trajectory id into the OD pair nodes produces origin-destination-set matrix. OD matrix simply counts the number of elements of the OD set matrix.
Desire-line set matrix is obtained from the set difference
between OD-set matrix and flow-set matrix. For instance, trajectory ids
{1,2,3,4,8,9} are passing node a to node b, however, only trajectory ids {1,
4,9} are passing direct link 
.
The remaining trajectories {2,3, 8} are using other alternative route to go
from node a to node b.
Taking only parts of direct links
from the desire-line-set matrix, we obtain alternative route flow set matrix.
Notice that not all direct links have alternative route flow. For instance,
links
,
,
and 
have only direct
link flows without alternative route flows (because no trajectory is passing
through those OD pairs using alternative route).
The alternative route flow matrix is simply the count of the members of set. The visualization of alternative flow matrix is also shown.
In this numerical example, it is clear that the relationship of equation (27) holds because
Matrix-Set
To derive the formulation in the paper, we use a combination of both matrix and set operations. In contrast to ordinary matrices in linear algebra whose elements are numbers or scalar values (which we call matrix-count), it is necessary to create our own mathematical concept of a matrix-set which is a matrix whose elements are sets. We use tilde on the top of a matrix to indicate matrix-set, such as Flow-set matrix and OD-set matrix. Operations on matrix-set are similar to both operations in matrix and set theory where the members in each matrix element must be unique and the order of the elements in a set is not important. We also extend the Hadamard multiplication to involve a matrix-set and a binary matrix. The Hadamard product between a matrix set and a binary matrix is computed by multiplication of corresponding elements, resulting either in the original element of the matrix set (if multiplied with 1) or an empty set (if multiplied by 0). We have developed special numerical library of matrix-set to serve the purpose of this research.